//路径的数目
class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        //思路
        //f(i,j)表示到达[i,j]的路径总数
        //因为只能往下或者往右移动
        //f(i,j)=f(i-1,j)+f(i,j+1);
        
        //初始值
        //第一行的每个位置都只有一种方式
        //第一列的每个位置都只有一种方式
        vector<vector<int>>ans(m,vector<int>(n));//二维数组的初始化
        for(int j=0;j<n;j++)
        {
            ans[0][j]=1;
        }
        for(int i=0;i<m;i++)
        {
            ans[i][0]=1;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                ans[i][j]=ans[i-1][j]+ans[i][j-1];
            }
        }
    return ans[m-1][n-1];
    }
};
//最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        //f(i,j) 到达[i,j]的的最小路径
        //f(i,j)=min( f(i-1,j) , f(i,j-1) )+val
        //第一行 f(i,x)=f(i,x-1)+val;
        if(grid.size()==0) return 0;
        vector<vector<int>>result(grid);
        int m=result.size();
        int n=result[0].size();
        //初始化第一行
        for(int j=1;j<n;j++)
        {
            result[0][j]=result[0][j-1]+grid[0][j];
        }
        //初始化第一列
        for(int i=1;i<m;i++)
        {
            result[i][0]=result[i-1][0]+grid[i][0];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                result[i][j]=min(result[i-1][j],result[i][j-1])+grid[i][j];
            }
        }
        return result[m-1][n-1];
    }
};
///不同路径2
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) dp[i][0]=1;
        for(int j=0;j<n&&obstacleGrid[0][j]==0;j++) dp[0][j]=1;
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    return dp[m-1][n-1];

    }
};
